//
//  ViewController.swift
//  Stack
//
//  Created by YC on 2018/7/26.
//  Copyright © 2018年 YC. All rights reserved.
//

import UIKit

class ViewController: UIViewController {
    private var stack = YCStack<Int>()
    
    override func viewDidLoad() {
        super.viewDidLoad()

//        var num = 0x126
//        let radix = 10
//
//        while num > 0 {
//            self.stack.push(num % radix)
//            num /= radix
//        }
//
//        while self.stack.isEmpty == false {
//            print(self.stack.pop()!)
//        }
//
//        print(String.init(0x126, radix: 10, uppercase: true))
//
//        let prefix = Int(String("126"), radix: 16)
//        print("\(prefix!)")
        
        self.test()
    }

    override func didReceiveMemoryWarning() {
        super.didReceiveMemoryWarning()
    }
    
    func test() {
        let str = "(40.54 + 3.56) * 2 + (6 / (( 3 - 2 ) * 2) - 1) * 2+(40.54+3.56)*2+(6/((3-2)*2)-1)*2+(40.54+3.56)*2+(6/((3-2)*2)-1)*2+(40.54+3.56)*2+(6/((3-2)*2)-1)*2+(40.54+3.56)*2+(6/((3-2)*2)-1)*2+(40.54+3.56)*2+(6/((3-2)*2)-1)*2+(40.54+3.56)*2+(6/((3-2)*2)-1)*2+(40.54+3.56)*2+(6/((3-2)*2)-1)*2"
        
//        let str = "(6-3)*2%4"
        
//        let str = "(40.54+3.56)*2+(6/((3-2)*2)-1)*2"

        var s1 = self.infixToPostfix(str)
        print(s1)
        s1.reverse()
        print(self.postfixExpResult(with: s1)!)
        
        var s2 = self.infixToPostfix3(str)
        print(s2)
        s2.reverse()
        print(self.postfixExpResult(with: s2)!)
    }
    
    /**
     *  判断是否为操作符
     */
    private func isOperator(_ op: Character) -> Bool {
        switch op {
        case "+":fallthrough
        case "-":fallthrough
        case "*":fallthrough
        case "/":fallthrough
        case "%":fallthrough
        case "(":fallthrough
        case ")":
            return true
        default:
            return false
        }
    }
    
    /**
     * 计算后缀表达式的值
     */
    func postfixExpResult(with stack: YCStack<String>) -> Double? {
        var s1 = stack
        var s2 = YCStack<Double>()
        
        while s1.isEmpty == false {
            let top = s1.pop()!
            if let value = Double(top) {
                s2.push(value)
            } else {
                let right = s2.pop()!
                let left = s2.pop()!
                
                switch top {
                case "*":
                    s2.push(left * right)
                case "/":
                    s2.push(left / right)
                case "%":
                    s2.push(left.truncatingRemainder(dividingBy: right))
                case "+":
                    s2.push(left + right)
                case "-":
                    s2.push(left - right)
                default:
                    break
                }
            }
        }
        return s2.peek()
    }
    
    /**
     * 中缀表达式转后缀表达式
     （1）遇到数字，则直接输出；
     （2）遇到左括号，则左括号进栈；
     （3）遇到右括号，从栈顶开始依次输出所有运算符，直到遇到左括号，这个左括号也出栈；
     （4）遇到加号或减号，从栈顶开始依次输出所有运算符，直到遇到左括号，但此时这个左括号不出栈，并且当前运算符进栈；
     （5）遇到乘号或除号，如果栈顶是乘号或除号，则输出，否则不输出，并且当前运算符进栈。
     */
    func infixToPostfix(_ exp: String) -> YCStack<String> {
        var s1 = YCStack<String>()
        var s2 = YCStack<String>()
        
        var value = ""
        for c in exp {
            if (c >= "0" && c <= "9") || c == "." {
                value.append(c)
            } else if self.isOperator(c) {
                // 数字进栈
                if value.count > 0 {
                    s1.push(value)
                    value = ""
                }
                
                switch c {
                case "(":
                    s2.push("\(c)")
                case ")":
//                    while s2.isEmpty == false {
//                        if s2.peek() == "(" {
//                            s2.pop()
//                            break
//                        }
//
//                        if let op = s2.pop() {
//                            s1.push(op)
//                        }
//                    }
                    // 右括号,运算符依次出栈,并写入到s1.
                    while s2.isEmpty == false && s2.peek() != "(" {
                        if let op = s2.pop() {
                            s1.push(op)
                        }
                    }
                    // 删除栈顶左括号.
                    s2.pop()
                case "+": fallthrough
                case "-":
                    while s2.isEmpty == false && s2.peek() != "(" {
                        if let top = s2.pop() {
                            s1.push(top)
                        }
                    }
                    s2.push("\(c)")
                case "*": fallthrough
                case "/": fallthrough
                case "%":
                    while s2.isEmpty == false && (s2.peek() == "*" || s2.peek() == "/" || s2.peek() == "%") {
                        if let op = s2.pop() {
                            s1.push(op)
                        }
                    }
                    s2.push("\(c)")
                default:
                    break
                }
            }
        }
        
        if value.count > 0 {
            s1.push(value)
        }
        
        while s2.isEmpty == false {
            if let op = s2.pop() {
                s1.push(op)
            }
        }
        
        return s1
    }


    /**
     *  获取操作符优先级
     *  inside == true,表示栈内优先级
     *  inside == false,表示栈外优先级
     */
    private func getPriority(_ op: String?, inside: Bool) -> Int {
        
        guard op != nil else {
            return 0
        }
        
        switch op! {
        case "+":fallthrough
        case "-":
            return inside ? 3 : 2
        case "*":fallthrough
        case "/":fallthrough
        case "%":
            return inside ? 5 : 4
        case "(":
            return inside ? 1 : 6
        case ")":
            return inside ? 6 : 1
        default:
            return 0
        }
    }

    func infixToPostfix2(_ exp: String) -> YCStack<String> {
        var s1 = YCStack<String>()
        var s2 = YCStack<String>()
        
        var value = ""
        for c in exp {
            if (c >= "0" && c <= "9") || c == "." {
                value.append(c)
            } else if self.isOperator(c) {
                // 数字进栈
                if value.count > 0 {
                    s1.push(value)
                    value = ""
                }

                if c == ")" {
                    while s2.isEmpty == false && s2.peek() != "(" {
                        if let top = s2.pop() {
                            s1.push(top)
                        }
                    }
                    s2.pop()
                    continue
                }
                
                if self.getPriority("\(c)", inside: false) > self.getPriority(s2.peek(), inside: true) {
                    s2.push("\(c)")
                    continue
                } else {
                    while s2.isEmpty == false && (self.getPriority("\(c)", inside: false) < self.getPriority(s2.peek()!, inside: true)) {
                        if let top = s2.pop() {
                            s1.push(top)
                        }
                    }
                    s2.push("\(c)")
                    continue
                }
            }
        }
        
        if value.count > 0 {
            s1.push(value)
        }
        
        while s2.isEmpty == false {
            if let op = s2.pop() {
                s1.push(op)
            }
        }
        
        return s1
    }
    
    private func precedence(with op: String?) -> Int {
        
        guard op != nil else {
            return 0
        }
        
        switch op! {
        case "+": fallthrough
        case "-":
            return 1
        case "*": fallthrough
        case "/": fallthrough
        case "%":
            return 2
        default:
            return 0
        }
    }
    
    func infixToPostfix3(_ exp: String) -> YCStack<String> {
        var s1 = YCStack<String>()
        var s2 = YCStack<String>()
        
        var value = ""
        for c in exp {
            // 当前为数字继续循环
            if (c >= "0" && c <= "9") || c == "." {
                value.append(c)
            } else if self.isOperator(c) {
                // 数字进栈
                if value.count > 0 {
                    s1.push(value)
                    value = ""
                }
                
                switch c {
                case "(":
                    // 左括号直接进栈.
                    s2.push("\(c)")
                case ")":
                    // 右括号,运算符依次出栈,并写入到s1.
                    while s2.isEmpty == false && s2.peek() != "(" {
                        if let op = s2.pop() {
                            s1.push(op)
                        }
                    }
                    // 删除栈顶左括号.
                    s2.pop()
                case "+": fallthrough
                case "-": fallthrough
                case "*": fallthrough
                case "/": fallthrough
                case "%":
                    // 使暂存在s2栈顶的不低于c优先级的运算符依次出栈并写入s1.
                    while self.precedence(with: s2.peek()) >= self.precedence(with: "\(c)") {
                        if let op = s2.pop() {
                            s1.push(op)
                        }
                    }
                    
                    s2.push("\(c)")
                default:
                    break
                }
            }
        }
        
        if value.count > 0 {
            s1.push(value)
        }
        
        while s2.isEmpty == false {
            if let op = s2.pop() {
                s1.push(op)
            }
        }
        
        return s1
    }
}

